package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-12-20
 * 最长公共子序列
 */
public class LongestCommonSubsequence
{

    /**
     * 主
     * \
     * 输入：text1 = "abcde", text2 = "ace"
     * 输出：3
     * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
     * \
     * 输入：text1 = "abc", text2 = "abc"
     * 输出：3
     * 解释：最长公共子序列是 "abc" ，它的长度为 3 。
     * \
     * 输入：text1 = "abc", text2 = "def"
     * 输出：0
     * 解释：两个字符串没有公共子序列，返回 0 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        LongestCommonSubsequence longestCommonSubsequence = new LongestCommonSubsequence();
        String text1 = "abcde";
        String text2 = "ace";
        System.out.println(longestCommonSubsequence.longestCommonSubsequence(text1, text2));
    }

    /**
     * 最长公共子序列
     * 动态规划
     * @param text1 文本1
     * @param text2 文本2
     * @return int
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        //初始位默认为0
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    //相等时，即是前一次的最长公共数+1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //不相等，取两者最大值。对于 ace和 bc而言，他们的最长公共子序列的长度取其中的而最长数， ace 和 b 的最长公共子序列长度0 与 ac 和 bc的最长公共子序列长度1 的最大值，即 1。
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
